In this section, we further refine our \(\alpha\)-MC. In particular, we shall study SARSA and Q-learning, that may handle infinite episode lengths.

Recall the update rule used in \(\alpha\)-MC

\[ V(s_t) \xleftarrow{} V(s_t) + \alpha(g^{(m)}_t - V(s_t)) \]

We have this \(g^{(m)}_t\) term, that requires knowing the reward until the end of the episode. Bootstrapping refers to the technique of estimating \(g_t\) using our existing value estimate.

In particular, we have that

\[ g_t \approx \sum_{k=1}^{T-t} \gamma^k R_{k+t} \approx \sum_{k=1}^{min(T - t, n)} \gamma^k R_{k+t} + \gamma^n V(s_{t+n}) \]

where instead of delaying until the end of the episode, we delay \(n\) steps before updating the rewards.

We may now discuss three algorithms implementing of TD learning.

First, n-step SARSA, (\(s_t, a_t, r_t, s_{t+1}, a_{t+1}\)), directly applies the TD formula into a MRP (states \(\leftarrow\) state-action pairs).

\begin{align} g^{(m)}_t &\xleftarrow{} \sum_{k=1}^{min(T - t, n)} \gamma^k R^{(m)}_{k+t} + \gamma^n v(s^{(m)}_{t+n}, a^{(m)}_{t+n}) \\ v(s^{(m)}_t, a^{(m)}_t) &\xleftarrow{} (1 - \alpha) v(s^{(m)}_t, a^{(m)}_t) + \alpha g^{(m)}_t \end{align}

To reduce the sampling error, we may take the following goal functions, used in expected SARSA and Q-learning respectively

\begin{align} g^{(m)}_t &\xleftarrow{} \sum_{k=1}^{min(T - t, n)} \gamma^k R^{(m)}_{k+t} + \gamma^n \sum_a v(s^{(m)}_{t+n}, a) \pi(a \mid s^{(m)}_{t+n}) \\ g^{(m)}_t &\xleftarrow{} \sum_{k=1}^{min(T - t, n)} \gamma^k R^{(m)}_{k+t} + \gamma^n \mathrm{max}_a v(s^{(m)}_{t+n}, a) \end{align}

\(\alpha\)-MC is an algorithm that updates the values linearly to the difference in rewards. This is exactly what the method for minimizing least sqaures does:

• \(E(x, \hat{x}) = \sum (x - \hat{x})^2\)
• \(E'(x, \hat{x}) = \sum 2 (x - \hat{x})\)
• \(\hat{x} \xleftarrow{} \hat{x} + \alpha E'(x, \hat{x}) = \hat{x} + \alpha (x - \hat{x})\)

However, (1-step) TD learning finds the method of moments estimator (same as MLE) of the reward.

• \(\hat{p}(s', r | s) = \frac{C(s', r \mid s)}{C(s)}\)

Formally, these analysis only work on batched learning, but the implementation simply approximates the batched, so we expect similar results. As TD more directly targets the reward, it generally achieves a faster or stronger convergence.

The Cliff Walking example shown in the video is particuarly insightful.

Using an \(\epsilon\)-Greedy process, SARSA recognizes that standing near the cliff is very risky.

However, as \(Q\)-learning does not have this \(epsilon\) chance of walking into the cliff, it is able to learn the optimal path. This shows the strength of off policy methods, taking advantage of importance sampling.

Further, expected SARSA picks somewhere in the middle.

See Eligibility Traces for a modification to the existing MC/TD algorithms to improve learning efficiency.

Home 1 2 3 4(b) 5 6 Next